/***************************************************
 * @Author: OBKoro1
 * @Create: 2020-04-05
 * @LastEditors: OBKoro1
 * @LastEditTime: 2020-04-05
 * @FilePath: \leetcode-exercise\3-无重复字符串的最长子串\test2.c
 * 思路：
 * 这道题主要用到思路是：滑动窗口
 * 什么是滑动窗口？
 * 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
 * 如何移动？
 * 我们只要把队列的左边的元素移出就行了，直到满足题目要求！
 * 一直维持这样的队列，找出队列出现最长的长度时候，求出解！
 * 具体题解思路见印象笔记
 ****************************************************/
#define MAX 1000
typedef struct
{
    int key;
    char val;
} HASH_MAP;

HASH_MAP map[MAX];
int lengthOfLongestSubstring(char *s)
{
    int len = strlen(s);
    int idx;
    int iidx;
    int hash_size = 0;
    int flag;
    int start = 0;
    int maxlen = 0;
    memset(map, 0, sizeof(map));

    for (idx = 0; idx < len; idx++)
    {
        flag = 0;
        for (iidx = 0; iidx <= hash_size; iidx++)
        {
            // 遍历hash map中是否存在对应的元素
            if (map[iidx].val == s[idx])
            {
                flag = 1;
                break;
            }
        }

        if (flag == 0)
        {
            //printf("s[%d] %c hash-size %d \n", idx, s[idx], hash_size);
            // 不存在该元素，则更新hash-map
            map[hash_size].val = s[idx];
            map[hash_size].key = idx + 1;
            hash_size++;
        }
        else
        {
            //printf("idx %d hash[%c] key %d \n", idx, s[idx], map[iidx].key);
            //更新滑动窗口的起始位置和hash-map的索引位置
            //printf("update start - old-start %d map[%c].key: %d\n", start, s[idx], map[iidx].key);
            start = start > map[iidx].key ? start : map[iidx].key;
            //printf("start : %d\n", start);
            // start 的约束 start = max(map(s).key+1 , start)
            map[iidx].key = idx + 1;
        }
        maxlen = (idx - start + 1) > maxlen ? (idx - start + 1) : maxlen;
        //printf("maxlen %d\n", maxlen);
    }
    return maxlen;
}
